class Solution:
    def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
        mod = 1000000007
        a = [[0] * (one + 1) for _ in range(zero + 1)]
        b = [[0] * (one + 1) for _ in range(zero + 1)]
        for i in range(min(zero, limit) + 1):
            a[i][0] = 1
        for i in range(min(one, limit) + 1):
            b[0][i] = 1
        for i in range(1, zero + 1):
            for j in range(1, one + 1):
                a[i][j] += b[i - 1][j]
                a[i][j] += (
                    a[i - 1][j] - b[i - 1 - limit][j] if i > limit else a[i - 1][j]
                )
                b[i][j] += a[i][j - 1]
                b[i][j] += (
                    b[i][j - 1] if j <= limit else b[i][j - 1] - a[i][j - 1 - limit]
                )
                a[i][j] = (a[i][j] + mod) % mod
                b[i][j] = (b[i][j] + mod) % mod
        return (a[zero][one] + b[zero][one]) % mod


s = Solution()
print(s.numberOfStableArrays(zero=1, one=1, limit=2) == 2)
print(s.numberOfStableArrays(zero=1000, one=1000, limit=2000) == 72475738)


class Solution:
    def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
        mod = 1000000007
        a = [[[0] * 2 for _ in range(one + 1)] for _ in range(zero + 1)]
        for i in range(min(zero, limit) + 1):
            a[i][0][0] = 1
        for i in range(min(one, limit) + 1):
            a[0][i][1] = 1
        for i in range(1, zero + 1):
            for j in range(1, one + 1):
                a[i][j][0] += a[i - 1][j][1] + a[i - 1][j][0]
                a[i][j][1] += a[i][j - 1][0] + a[i][j - 1][1]
                if i > limit:
                    a[i][j][0] -= a[i - 1 - limit][j][1]
                if j > limit:
                    a[i][j][1] -= a[i][j - 1 - limit][0]
                for k in range(2):
                    a[i][j][k] = (a[i][j][k] + mod) % mod

        return sum(a[zero][one]) % mod


s = Solution()
print(s.numberOfStableArrays(zero=1, one=1, limit=2) == 2)
print(s.numberOfStableArrays(zero=1000, one=1000, limit=2000) == 72475738)
